/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* getmid(ListNode* cur)
    {
        // 1 2 3 4
        ListNode* fast;
        ListNode* slow;
        fast =  cur;
        slow = cur;
        while(fast->next&&fast->next->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }//当循环结束的时候slow的next指向的就是中间点指针
        ListNode* next= slow->next;
        slow->next = nullptr;//将这两段链表分开完成分治
        return next;//再返回中间点
    }//使用快慢指针完成这一段寻找中间点的过程
    ListNode* mergesort(ListNode* head1,ListNode* head2)
    {
        ListNode* newhead = new ListNode();
        ListNode* cur = newhead;
        while(head1&&head2)
        {
            if(head1->val<head2->val)
            {
                cur->next = head1;
                cur = cur->next;
                head1 = head1->next;
            }
            else
            {
                 cur->next = head2;
                cur = cur->next;
                head2 = head2->next;
            }
        }
        cur->next = head1?head1:head2;//将后序的后半部分放入到cur中
        ListNode* ret = newhead->next;
        delete newhead;
        return ret;
    }//将两个有序链表合并为一个有序链表
    ListNode* sortList(ListNode* head) 
    {
        if(head == nullptr||head->next == nullptr)
        {
            return head;
        }//不需要进行排序的情况
        //第一种解法使用非常数级别的空间复杂度，原理为归并排序
        //首先将链表分离为两个有序链表，然后再将两个有序链表合并为一个有序链表
        //如何分离呢？方法就是使用快慢指针寻找中间节点的方式
        ListNode* mid =  getmid(head);//得到这段链表的中间节点
        head = sortList(head);//再去完成前半部分的排序
        mid = sortList(mid);//再去完成后半部分的排序
        return mergesort(head,mid);//再将这两个部分合并为一个有序链表
    }
};